// #define print(...)

class Solution {
public:
bool isValid(string s) {
    if(s.size()%2) return false;
    list<char> stk;
    unordered_map<char,char> match = {
        {'(', ')'},
        {'[', ']'},
        {'{', '}'},
    };
    for(auto &c:s){
        if(match.count(c)){
            stk.push_back(c);
        }else{
            if(stk.empty() || match[stk.back()] != c)
                return false;
            stk.pop_back();
        }
    }
    return stk.empty();
}
};
